package P169.P229;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author DJ同学
 * @Date 2021/2/17 16:21
 * @Version 1.0
 * @Name 求众数II
 * @Problem https://leetcode-cn.com/problems/majority-element-ii/
 */
public class Solution {

    @Test
    public void test01(){
        int[] nums = new int[]{3,3,1,1,1,1,2,4,4,3,3,3,4,4};
        System.out.println(majorityElement(nums));
    }

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int card_num1=nums[0];
        int cnt1=0;
        int card_num2=nums[0];
        int cnt2=0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==card_num1){
                cnt1++;
                continue;
            }
            if(nums[i]==card_num2){
                cnt2++;
                continue;
            }
            else if(cnt1==0){
                card_num1=nums[i];
                cnt1=1;
                continue;
            }
            else if(cnt2==0) {
                card_num2=nums[i];
                cnt2=1;
                continue;
            }
            cnt1--;
            cnt2--;
        }
        //处理 题目中并没有说 一定有2个众数
        int cur_cnt1=0;
        int cur_cnt2=0;
        for(int i=0;i<nums.length;i++){
            if(card_num1==nums[i]){
                cur_cnt1++;
            }
            //else if的作用避免出现card_num1==card_num2
            else if(card_num2==nums[i]){
                cur_cnt2++;
            }
        }
//        System.out.println(card_num1);
        if(cur_cnt1>nums.length/3){
            res.add(card_num1);
        }
//        System.out.println(card_num2);
        if(cur_cnt2>nums.length/3){
            res.add(card_num2);
        }
        return res;
    }
}
